# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.res = root.val
        self.search(root)
        return self.res

    def search(self, root: TreeNode) -> int:
        if not root:
            return 0
        elif not root.left and not root.right:
            self.res = max(self.res, root.val)
            return root.val > 0 and root.val
        else:
            left, right = self.search(root.left), self.search(root.right)
            self.res = max(self.res, left + right + root.val)
            mid_return = max(left, right) + root.val
            return mid_return > 0 and mid_return
